MAYBE 117.402
H-Termination proof of /home/matraf/haskell/eval_FullyBlown_Fast/empty.hs
H-Termination of the given Haskell-Program with start terms could not be shown:
↳ HASKELL
↳ BR
mainModule Main
| ((enumFromTo :: Float -> Float -> [Float]) :: Float -> Float -> [Float]) |
module Main where
Replaced joker patterns by fresh variables and removed binding patterns.
↳ HASKELL
↳ BR
↳ HASKELL
↳ COR
mainModule Main
| ((enumFromTo :: Float -> Float -> [Float]) :: Float -> Float -> [Float]) |
module Main where
Cond Reductions:
The following Function with conditions
is transformed to
undefined0 | True | = undefined |
undefined1 | | = undefined0 False |
The following Function with conditions
takeWhile | p [] | = [] |
takeWhile | p (x : xs) | |
is transformed to
takeWhile | p [] | = takeWhile3 p [] |
takeWhile | p (x : xs) | = takeWhile2 p (x : xs) |
takeWhile1 | p x xs True | = x : takeWhile p xs |
takeWhile1 | p x xs False | = takeWhile0 p x xs otherwise |
takeWhile0 | p x xs True | = [] |
takeWhile2 | p (x : xs) | = takeWhile1 p x xs (p x) |
takeWhile3 | p [] | = [] |
takeWhile3 | vz wu | = takeWhile2 vz wu |
↳ HASKELL
↳ BR
↳ HASKELL
↳ COR
↳ HASKELL
↳ NumRed
mainModule Main
| ((enumFromTo :: Float -> Float -> [Float]) :: Float -> Float -> [Float]) |
module Main where
Num Reduction: All numbers are transformed to thier corresponding representation with Pos, Neg, Succ and Zero.
↳ HASKELL
↳ BR
↳ HASKELL
↳ COR
↳ HASKELL
↳ NumRed
↳ HASKELL
↳ Narrow
↳ Narrow
mainModule Main
| (enumFromTo :: Float -> Float -> [Float]) |
module Main where
Haskell To QDPs
↳ HASKELL
↳ BR
↳ HASKELL
↳ COR
↳ HASKELL
↳ NumRed
↳ HASKELL
↳ Narrow
↳ AND
↳ QDP
↳ QDPSizeChangeProof
↳ QDP
↳ QDP
↳ QDP
↳ QDP
↳ QDP
↳ Narrow
Q DP problem:
The TRS P consists of the following rules:
new_not(Succ(wv191200), Succ(wv194700)) → new_not(wv191200, wv194700)
R is empty.
Q is empty.
We have to consider all minimal (P,Q,R)-chains.
By using the subterm criterion [20] together with the size-change analysis [32] we have proven that there are no infinite chains for this DP problem. From the DPs we obtained the following set of size-change graphs:
- new_not(Succ(wv191200), Succ(wv194700)) → new_not(wv191200, wv194700)
The graph contains the following edges 1 > 1, 2 > 2
↳ HASKELL
↳ BR
↳ HASKELL
↳ COR
↳ HASKELL
↳ NumRed
↳ HASKELL
↳ Narrow
↳ AND
↳ QDP
↳ QDP
↳ QDPSizeChangeProof
↳ QDP
↳ QDP
↳ QDP
↳ QDP
↳ Narrow
Q DP problem:
The TRS P consists of the following rules:
new_primPlusNat(Succ(wv191800), Succ(wv189400)) → new_primPlusNat(wv191800, wv189400)
R is empty.
Q is empty.
We have to consider all minimal (P,Q,R)-chains.
By using the subterm criterion [20] together with the size-change analysis [32] we have proven that there are no infinite chains for this DP problem. From the DPs we obtained the following set of size-change graphs:
- new_primPlusNat(Succ(wv191800), Succ(wv189400)) → new_primPlusNat(wv191800, wv189400)
The graph contains the following edges 1 > 1, 2 > 2
↳ HASKELL
↳ BR
↳ HASKELL
↳ COR
↳ HASKELL
↳ NumRed
↳ HASKELL
↳ Narrow
↳ AND
↳ QDP
↳ QDP
↳ QDP
↳ QDPSizeChangeProof
↳ QDP
↳ QDP
↳ QDP
↳ Narrow
Q DP problem:
The TRS P consists of the following rules:
new_primMulNat(Succ(wv3000), wv18940) → new_primMulNat(wv3000, wv18940)
R is empty.
Q is empty.
We have to consider all minimal (P,Q,R)-chains.
By using the subterm criterion [20] together with the size-change analysis [32] we have proven that there are no infinite chains for this DP problem. From the DPs we obtained the following set of size-change graphs:
- new_primMulNat(Succ(wv3000), wv18940) → new_primMulNat(wv3000, wv18940)
The graph contains the following edges 1 > 1, 2 >= 2
↳ HASKELL
↳ BR
↳ HASKELL
↳ COR
↳ HASKELL
↳ NumRed
↳ HASKELL
↳ Narrow
↳ AND
↳ QDP
↳ QDP
↳ QDP
↳ QDP
↳ QDPSizeChangeProof
↳ QDP
↳ QDP
↳ Narrow
Q DP problem:
The TRS P consists of the following rules:
new_not0(wv300, Succ(wv18950), Succ(wv4000), wv31, wv41) → new_not0(wv300, wv18950, wv4000, wv31, wv41)
R is empty.
Q is empty.
We have to consider all minimal (P,Q,R)-chains.
By using the subterm criterion [20] together with the size-change analysis [32] we have proven that there are no infinite chains for this DP problem. From the DPs we obtained the following set of size-change graphs:
- new_not0(wv300, Succ(wv18950), Succ(wv4000), wv31, wv41) → new_not0(wv300, wv18950, wv4000, wv31, wv41)
The graph contains the following edges 1 >= 1, 2 > 2, 3 > 3, 4 >= 4, 5 >= 5
↳ HASKELL
↳ BR
↳ HASKELL
↳ COR
↳ HASKELL
↳ NumRed
↳ HASKELL
↳ Narrow
↳ AND
↳ QDP
↳ QDP
↳ QDP
↳ QDP
↳ QDP
↳ QDPSizeChangeProof
↳ QDP
↳ Narrow
Q DP problem:
The TRS P consists of the following rules:
new_not1(wv300, Succ(wv18940), Succ(wv4000), wv31, wv41) → new_not1(wv300, wv18940, wv4000, wv31, wv41)
R is empty.
Q is empty.
We have to consider all minimal (P,Q,R)-chains.
By using the subterm criterion [20] together with the size-change analysis [32] we have proven that there are no infinite chains for this DP problem. From the DPs we obtained the following set of size-change graphs:
- new_not1(wv300, Succ(wv18940), Succ(wv4000), wv31, wv41) → new_not1(wv300, wv18940, wv4000, wv31, wv41)
The graph contains the following edges 1 >= 1, 2 > 2, 3 > 3, 4 >= 4, 5 >= 5
↳ HASKELL
↳ BR
↳ HASKELL
↳ COR
↳ HASKELL
↳ NumRed
↳ HASKELL
↳ Narrow
↳ AND
↳ QDP
↳ QDP
↳ QDP
↳ QDP
↳ QDP
↳ QDP
↳ MNOCProof
↳ Narrow
Q DP problem:
The TRS P consists of the following rules:
new_takeWhile1(wv1699, wv1842, wv1841, wv1844, wv1843) → new_takeWhile1(wv1699, new_ps(wv1844), new_sr(wv1843), new_ps(wv1844), new_sr(wv1843))
The TRS R consists of the following rules:
new_primPlusNat0(Zero, Zero) → Zero
new_primPlusNat1(Succ(wv19180), wv18940) → Succ(Succ(new_primPlusNat0(wv19180, wv18940)))
new_ps(Neg(Zero)) → Pos(Succ(Zero))
new_ps(Pos(wv18440)) → Pos(new_primPlusNat2(wv18440))
new_primMulNat0(Succ(wv3000), wv18940) → new_primPlusNat1(new_primMulNat0(wv3000, wv18940), wv18940)
new_primPlusNat1(Zero, wv18940) → Succ(wv18940)
new_ps(Neg(Succ(Zero))) → Pos(Zero)
new_primMulNat1(Zero) → Zero
new_primMulNat0(Zero, wv18940) → Zero
new_ps(Neg(Succ(Succ(wv1844000)))) → Neg(Succ(wv1844000))
new_primMulNat1(Succ(wv184300)) → new_primPlusNat1(new_primMulNat0(wv184300, Zero), Zero)
new_primPlusNat0(Zero, Succ(wv189400)) → Succ(wv189400)
new_primPlusNat0(Succ(wv191800), Zero) → Succ(wv191800)
new_sr(Neg(wv18430)) → Neg(new_primMulNat1(wv18430))
new_primPlusNat0(Succ(wv191800), Succ(wv189400)) → Succ(Succ(new_primPlusNat0(wv191800, wv189400)))
new_sr(Pos(wv18430)) → Pos(new_primMulNat1(wv18430))
new_primPlusNat2(wv18440) → new_primPlusNat1(wv18440, Zero)
The set Q consists of the following terms:
new_ps(Neg(Succ(Zero)))
new_sr(Neg(x0))
new_ps(Neg(Succ(Succ(x0))))
new_ps(Pos(x0))
new_primPlusNat1(Zero, x0)
new_primMulNat0(Succ(x0), x1)
new_primPlusNat0(Succ(x0), Zero)
new_primMulNat1(Succ(x0))
new_sr(Pos(x0))
new_primMulNat0(Zero, x0)
new_primPlusNat0(Zero, Zero)
new_primPlusNat0(Succ(x0), Succ(x1))
new_primPlusNat1(Succ(x0), x1)
new_ps(Neg(Zero))
new_primPlusNat2(x0)
new_primMulNat1(Zero)
new_primPlusNat0(Zero, Succ(x0))
We have to consider all minimal (P,Q,R)-chains.
We use the modular non-overlap check [17] to decrease Q to the empty set.
↳ HASKELL
↳ BR
↳ HASKELL
↳ COR
↳ HASKELL
↳ NumRed
↳ HASKELL
↳ Narrow
↳ AND
↳ QDP
↳ QDP
↳ QDP
↳ QDP
↳ QDP
↳ QDP
↳ MNOCProof
↳ QDP
↳ NonTerminationProof
↳ Narrow
Q DP problem:
The TRS P consists of the following rules:
new_takeWhile1(wv1699, wv1842, wv1841, wv1844, wv1843) → new_takeWhile1(wv1699, new_ps(wv1844), new_sr(wv1843), new_ps(wv1844), new_sr(wv1843))
The TRS R consists of the following rules:
new_primPlusNat0(Zero, Zero) → Zero
new_primPlusNat1(Succ(wv19180), wv18940) → Succ(Succ(new_primPlusNat0(wv19180, wv18940)))
new_ps(Neg(Zero)) → Pos(Succ(Zero))
new_ps(Pos(wv18440)) → Pos(new_primPlusNat2(wv18440))
new_primMulNat0(Succ(wv3000), wv18940) → new_primPlusNat1(new_primMulNat0(wv3000, wv18940), wv18940)
new_primPlusNat1(Zero, wv18940) → Succ(wv18940)
new_ps(Neg(Succ(Zero))) → Pos(Zero)
new_primMulNat1(Zero) → Zero
new_primMulNat0(Zero, wv18940) → Zero
new_ps(Neg(Succ(Succ(wv1844000)))) → Neg(Succ(wv1844000))
new_primMulNat1(Succ(wv184300)) → new_primPlusNat1(new_primMulNat0(wv184300, Zero), Zero)
new_primPlusNat0(Zero, Succ(wv189400)) → Succ(wv189400)
new_primPlusNat0(Succ(wv191800), Zero) → Succ(wv191800)
new_sr(Neg(wv18430)) → Neg(new_primMulNat1(wv18430))
new_primPlusNat0(Succ(wv191800), Succ(wv189400)) → Succ(Succ(new_primPlusNat0(wv191800, wv189400)))
new_sr(Pos(wv18430)) → Pos(new_primMulNat1(wv18430))
new_primPlusNat2(wv18440) → new_primPlusNat1(wv18440, Zero)
Q is empty.
We have to consider all (P,Q,R)-chains.
We used the non-termination processor [17] to show that the DP problem is infinite.
Found a loop by semiunifying a rule from P directly.
The TRS P consists of the following rules:
new_takeWhile1(wv1699, wv1842, wv1841, wv1844, wv1843) → new_takeWhile1(wv1699, new_ps(wv1844), new_sr(wv1843), new_ps(wv1844), new_sr(wv1843))
The TRS R consists of the following rules:
new_primPlusNat0(Zero, Zero) → Zero
new_primPlusNat1(Succ(wv19180), wv18940) → Succ(Succ(new_primPlusNat0(wv19180, wv18940)))
new_ps(Neg(Zero)) → Pos(Succ(Zero))
new_ps(Pos(wv18440)) → Pos(new_primPlusNat2(wv18440))
new_primMulNat0(Succ(wv3000), wv18940) → new_primPlusNat1(new_primMulNat0(wv3000, wv18940), wv18940)
new_primPlusNat1(Zero, wv18940) → Succ(wv18940)
new_ps(Neg(Succ(Zero))) → Pos(Zero)
new_primMulNat1(Zero) → Zero
new_primMulNat0(Zero, wv18940) → Zero
new_ps(Neg(Succ(Succ(wv1844000)))) → Neg(Succ(wv1844000))
new_primMulNat1(Succ(wv184300)) → new_primPlusNat1(new_primMulNat0(wv184300, Zero), Zero)
new_primPlusNat0(Zero, Succ(wv189400)) → Succ(wv189400)
new_primPlusNat0(Succ(wv191800), Zero) → Succ(wv191800)
new_sr(Neg(wv18430)) → Neg(new_primMulNat1(wv18430))
new_primPlusNat0(Succ(wv191800), Succ(wv189400)) → Succ(Succ(new_primPlusNat0(wv191800, wv189400)))
new_sr(Pos(wv18430)) → Pos(new_primMulNat1(wv18430))
new_primPlusNat2(wv18440) → new_primPlusNat1(wv18440, Zero)
s = new_takeWhile1(wv1699, wv1842, wv1841, wv1844, wv1843) evaluates to t =new_takeWhile1(wv1699, new_ps(wv1844), new_sr(wv1843), new_ps(wv1844), new_sr(wv1843))
Thus s starts an infinite chain as s semiunifies with t with the following substitutions:
- Matcher: [wv1841 / new_sr(wv1843), wv1843 / new_sr(wv1843), wv1842 / new_ps(wv1844), wv1844 / new_ps(wv1844)]
- Semiunifier: [ ]
Rewriting sequence
The DP semiunifies directly so there is only one rewrite step from new_takeWhile1(wv1699, wv1842, wv1841, wv1844, wv1843) to new_takeWhile1(wv1699, new_ps(wv1844), new_sr(wv1843), new_ps(wv1844), new_sr(wv1843)).
Haskell To QDPs